package problem56_Merge_Intervals;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class MySolution {
	public static void main(String[] args){
		MySolution solution =new MySolution();
		List<Interval> list=new LinkedList<>();
		list.add(solution.new Interval(1,3));
		list.add(solution.new Interval(2,6));
		list.add(solution.new Interval(8,10));
		list.add(solution.new Interval(15,18));
		System.out.println(solution.merge(list));
	}
	
	public List<Interval> merge(List<Interval> intervals) {
		List<Interval> result=new LinkedList<>();
		if(intervals.size()==0) return result;
		intervals.sort(new Comparator<Interval>(){
			@Override
			public int compare(Interval o1, Interval o2) {
				return Integer.compare(o1.start, o2.start);
			}
		});
		Interval last=intervals.get(0);
		for(Interval curr:intervals){
			if(curr.start>last.end){
				result.add(last);
				last=curr;
			}
			else if(curr.end>last.end){
				last.end=curr.end;
			}
		}
		result.add(last);
		return result;
	}

	public class Interval {
		int start;
		int end;

		public Interval() {
			start = 0;
			end = 0;
		}

		public Interval(int s, int e) {
			start = s;
			end = e;
		}

		@Override
		public String toString() {
			return "Interval [start=" + start + ", end=" + end + "]";
		}
		
	}
}
